class Solution {
public:
    vector<string> generateParenthesis(int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        string cur;
        vector<string> ans;
        generateHelper(0, n, 0, cur, ans);
        return ans;
    }

    void generateHelper(int depth, int n, int leftNum, string &cur, vector<string> &ans) {
        if (depth == n * 2) {
            ans.push_back(cur);
            return;
        }
        if (2 * n - depth <= leftNum || leftNum > 0) {
            cur += ')';
            generateHelper(depth + 1, n, leftNum - 1, cur, ans);
            cur.erase(cur.length() - 1, 1);
        }

        if (2 * n - depth > leftNum) {
            cur += '(';
            generateHelper(depth + 1, n, leftNum + 1, cur, ans);
            cur.erase(cur.length() - 1, 1);
        }
    }
};
